using System;
using System.Collections.Generic;
using System.Text;

namespace TicTacToe
{
    public class MinimaxAlgorithm : IGameAlgorithm
    {
        public int Solve(Board board)
        {
            int Omove = -1;
            int v = -2;
            int alpha = -2;
            int beta = 2;

            foreach (int i in board.GetValidMoves())
            {
                Board successor = (Board)board.Clone();
                successor[i] = BoardPlayer.Computer;
                int vTemp = Min_Value(successor, alpha, beta);
                // take max of min values
                if (vTemp > v)
                {
                    Omove = i;
                    v = vTemp;
                }
                if (v >= beta)
                    break;
                alpha = Max(alpha, v);
            }

            return Omove;
        }

        private int Max_Value(Board b, int alpha, int beta)
        {
            if (b.Evaluate(BoardPlayer.Player))
                return -1; // minimize
            if (b.Evaluate(BoardPlayer.Computer))
                return 1;  // maximize
            if (b.IsFull())
                return 0;

            int v = -2;
            foreach (int i in b.GetValidMoves())
            {
                Board s = (Board)b.Clone(); // successor
                s[i] = BoardPlayer.Computer;
                v = Max(v, Min_Value(s, alpha, beta));
                if (v >= beta)
                    return v;
                alpha = Max(alpha, v);
            }
            return v;
        }

        private int Min_Value(Board b, int alpha, int beta)
        {
            if (b.Evaluate(BoardPlayer.Player))
                return -1;  // minimize
            if (b.Evaluate(BoardPlayer.Computer))
                return 1;   // maximize
            if (b.IsFull())
                return 0;

            int v = 2;
            foreach (int i in b.GetValidMoves())
            {
                Board s = (Board)b.Clone(); //successor
                s[i] = BoardPlayer.Player;
                v = Min(v, Max_Value(s, alpha, beta));
                if (v <= alpha)
                    return v;
                beta = Min(beta, v);
            }
            return v;
        }

        private int Max(int a, int b)
        {
            return (a > b ? a : b);
        }

        private int Min(int a, int b)
        {
            return (a < b ? a : b);
        }
    }
}
